Graph Traversal
Q1.
Let U = \{1, 2, 3\}. Let 2^U denote the powerset of U. Consider an undirected graph G whose vertex set is 2^U. For any A,B \in 2^U, (A,B) is an edge in G if and only if (i) A \neq B, and (ii) either A \subseteq B or B \subseteq A. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A). If \phi denotes the empty set, then the cardinality of B(\phi ) is ____.Q2.
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?Q3.
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?Q5.
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?Q6.
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph isQ7.
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is______ .Q8.
Consider the following sequence of nodes for the undirected graph given below: 1.a b e f d g c 2.a b e f c g d 3.a d g e b c f 4.a d b c g e f A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which of the above is/are possible output(s)?Q9.
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.Q10.
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity